Many communications systems perform forward error correction (FEC) to improve data transmission accuracy and ensure data integrity. FEC helps reduce bit error rates (BER) in applications such as data storage, digital video broadcasts, and wireless communications. Reed-Solomon (RS) error-correcting codes are commonly used for FEC.
Referring now to FIG. 1, a first device 10-1 communicates with a second device 10-2 over a communications channel 12. The communications channel 12 may be, for example, an Ethernet network, a wireless local area network, a bus for a hard drive, etc. The communications channel 12 may represent a storage media (such as a hard drive), in which case there would be no second device 10-2. Instead, the communications channel would store data from the first device 10-1 (e.g., the read/write head and channel of a hard drive) and later provide the data to the first device 10-1. Or, in the case of a compact disc, the first device 10-1 (the CD recording device) would not need a RS decoder 18-1 and the second device 10-2 (a CD player) would not need a RS decoder 18-2.
The first device 10-1 includes components 14-1 that output signals to a Reed-Solomon (RS) encoder 16-1 and that receive signals from a RS decoder 18-1. Likewise, the second device 10-2 includes components 14-2 that output signals to a RS encoder 16-2 and that receive signals from a RS decoder 18-2. The components 14-1 of the first device 10-1 may be similar to or different than the components 14-2 of the second device 10-2. The RS encoders 16 encode data before the encoded data is output onto the communications channel 12. The encoding process adds redundant information to the data stream that allows the RS decoders 18 to possibly detect and correct errors in the received data.
Reed-Solomon error correction is a block coding scheme. This means that data symbols are encoded as a group. A symbol is often represented as a group of bits (e.g., a ten-bit symbol). The code dimension, k, is the number of data symbols encoded together. After encoding, the resultant block (known as a codeword) contains a greater number, n, of symbols, where n is termed the block length. The (n−k) additional symbols, known as ECC check symbols, allow a Reed-Solomon decoder to detect and correct errors in a transmission. With (n−k) set equal to 2t, the Reed-Solomon code can correct up to t random errors. The code has a minimum Hamming distance dmin=2t+1, which means that Reed-Solomon codes are maximum distance separable (MDS). If Ne is the number of random errors, a 2t Reed-Solomon code can correct all errors provided that Ne≦t. These errors are random in that neither their location within the codeword nor their magnitude is known.
If the location of an error is known, the error is termed an erasure. Error locations may be identified when certain properties of the communications channel indicate that a particular symbol was not transmitted successfully. A standard Reed-Solomon code can correct up to 2t erasures. The ability to correct twice as many erasures as errors can be understood as follows: while both location and magnitude must be determined for each random error, half of such information is already known for an erasure. A combination of errors and erasures can be corrected if the following inequality holds: Na+2Ne≦2t, where Na is the number of erasures.
Alternately, a burst of errors can be corrected, provided that the total length of the burst is less than 2t. This burst of errors is not simply a set of erasures, because the location of the error burst within the codeword is unknown. All that is known is that the errors are contiguous. An algorithm to recover this burst of errors is described in J. Chen & P. Owsley, “A Burst-Error-Correction Algorithm for Reed-Solomon Codes,” IEEE Trans. on Information Theory, Vol. 38, No. 6, November 1992. This algorithm fails, however, if the transmission contains one or more random errors that are not contiguous with the burst of errors.
For a mathematical foundation, Reed-Solomon codes operate over a finite field GF(2m). GF(q) is a Galois field with q elements, and each of the q elements can be represented by m bits. If n<2m−1 and n is not a factor of 2m−1, shortened RS codes can be used. A codeword vector of length n over GF(q) can be defined as c=(c0, c1, . . . , cn−1) where n=q−1. The codeword c can be represented as a polynomial
      c    ⁡          (      x      )        =            ∑              i        =        0                    n        -        1              ⁢                  ⁢                  c        i            ⁢                        x          i                .            Every codeword c is a multiple of a generator polynomial g(x), whereg(x)=(x−αm0)(x−αm0+1) . . . (x−αm0+2t−1).
The Fourier transform of the vector c is represented as C=(C0, C1, . . . , Cn−1), where
            C      j        =                  ∑                  i          =          0                          n          -          1                    ⁢                          ⁢                        c          i                ⁢                  α          ij                      ,      j    =    0    ,  1  ,  …  ⁢          ,      n    -    1  and α is a primitive element of GF(q). A t-error-correcting RS code is the collection of all vectors c with a Fourier transform satisfying Cm0=Cm0+1= . . . =Cm0+2t−1=0 for some integer m0. The Fourier transform C of c(x) has the same form as a polynomial evaluation of c(x) at x=α0, α1, . . . , αn−1. In other words, the Fourier transform coefficients are Cj=c(αj). A t-error-correcting RS code can also be described as the collection of all vectors c such that c(αm0)=c(αm0+1)= . . . =c(αm030 2t−1)=0.
An n-symbol codeword c from an RS encoder is transmitted over a communications channel, which may inject errors. A RS decoder receives an n-symbol vector v from the communications channel. The received vector, v, can be represented as v=c+e, where c is the transmitted codeword and e=(e0, e1, . . . , en−1) is the error vector induced by the channel. Each element ei is nonzero only when there is an error at the ith position.
When v is received, the transmitted codeword c and the error vector e are not known. It is known, however, that the Fourier transform of c satisfies Cm0= . . . =Cm0+2t−1=0. Because the Fourier transform is a linear transformation,Vi=Ci+Ei for i=0,1, . . . , n−1,where V and E are the Fourier transforms of the vectors v and e, respectively. Because codewords are defined such that Ci=0 for i=m0, m0+1, . . . , m0+2t−1, it follows that:Ei=Vi for i=m0,m0+1, . . . , m0+2t−1.Ei can therefore be computed from the received vector for i=m0, . . . , m0+2t−1. These Ei are denoted as Si=Ei+m0 for i=0, . . . , 2t−1, and are called syndromes.
The RS decoder next computes the error vector e from the 2t syndromes, a task which can be divided into two parts. First, the error locations are found. In other words, the decoder finds all i such that ei≠0. Second, the error values ei are determined for each of the error locations. Once e is known, the transmitted codeword c can be recovered by subtracting e from v. A fuller discussion of these steps is presented in R. E. Blahut, “Theory and Practice of Error Control Codes,” Addison-Wesley 1983, which is hereby incorporated by reference in its entirety.
Referring now to FIG. 2, a flow chart presents steps performed by a Reed-Solomon decoder according to the prior art are shown generally at 20. Control begins in step 22 where the RS decoder computes the syndromes. In step 24 the RS decoder computes an error locator polynomial. The error locator polynomial can be computed using a variety of suitable algorithms, including the Berlekamp-Massey algorithm (BMA), inversionless BMA (iBMA), and the Euclidean algorithm. iBMA is disclosed in “Efficient High-Speed Reed-Solomon Decoder,” U.S. patent application Ser. No. 10/305,091, filed Nov. 26, 2002, and “Error Evaluator For Inversionless Berlekamp-Massey Algorithm In Reed-Solomon Decoders,” U.S. patent application Ser. No. 10/292,181, filed Nov. 12, 2002, which are hereby incorporated by reference in their entirety.
In step 26 the RS decoder calculates an error evaluator polynomial, often based on the syndromes and the error locator polynomial. This is traditionally given by Γ(x)=S(x)Λ(x) mod x2t, where
      S    ⁡          (      x      )        =            ∑              i        =        0                              2          ⁢          t                -        1              ⁢                  ⁢                  S        i            ⁢              x        i            is the syndrome polynomial. In step 28 the RS decoder determines error locations by finding the zeroes of the error locator polynomial. This can be accomplished by, for example, Chien's search algorithm, which is disclosed in R. T. Chien, “Cyclic Decoding Procedure for the Bose-Chandhuri-Hocquenghem Codes,” I.E.E.E. Trans. on Information Theory, Vol. IT-10, pp. 357-63, October 1964, which is hereby incorporated by reference in its entirety. In step 30, the RS decoder calculates error values. Forney's algorithm is often used to find the error values, and is disclosed in G. D. Forney, “On Decoding BCH Codes,” I.E.E.E. Trans. on Information Theory, Vol. IT-11, pp. 549-57, October 1965, which is hereby incorporated by reference in its entirety. The steps 20 may be arranged in a pipelined structure.
Referring now to FIG. 3, a Reed-Solomon decoder 32 typically includes a syndrome calculator 34 and an error locator polynomial generator 36. The RS decoder 32 also includes an error evaluator polynomial generator 38, an error location finder 40, and an error value finder 42. Control modules 44 and storage devices 46 may also be used to control decoding and to store data values for use by the RS decoder 32. As can be appreciated, some of the components of the RS decoder 32 may share multipliers and/or other elements to reduce cost.
The RS decoder computes the error locator polynomial, which is defined as a polynomial
      Λ    ⁡          (      x      )        =            ∑              i        =        0            L        ⁢                  Λ        i            ⁢              x        i            satisfying the following conditions:Λ(0)=1; Λ(α−i)=0 if and only if ei≠0.Error locations are obtained by finding the zeros of Λ(x). The Berlekamp-Massey Algorithm (BMA) iteratively computes the error locator polynomial Λ(x). If the number of errors is less than or equal to t, the error locator polynomial is the polynomial of lowest degree that produces the syndrome sequence S0, S1, . . . , S2t−1. If the number of errors is greater than t, the BMA still generates the polynomial of lowest degree that produces the syndrome sequence. However, this polynomial is usually not a locator polynomial, and the decoding algorithm fails.
Referring now to FIG. 4, steps taken by an exemplary BMA implementation are depicted. The syndrome sequence S0, S1, . . . , S2t−1 and the number t are received as inputs. Control begins in step 100 where variables are initialized (Λ(x)=1, B(x)=1, r=0, L=0). In one embodiment, if erasure positions are known, Λ(x) and B(x) may be initialized to the erasure locator polynomial having zeroes at the known erasure locations. Further, L and r may be initialized to the number of erasures. In step 104, if r equals two times t, control transfers to step 108 and ends. Otherwise, control transfers to step 110 where the discrepancy
  Δ  =            ∑              i        =        0            L        ⁢                  ⁢                  Λ        i            ⁢              S                  r          -          i                    is computed.
If Δ≠0 and 2L≦r in step 112, control transfers to step 114; otherwise control transfers to step 116. In step 114 B(x) is set to Δ−1Λ(x) and Λ(x) is simultaneously set to Λ(x)−ΔxB(x). L is updated to r+1−L, and control continues with step 118. In step 116 B(x) is set to xB(x), Λ(x) is simultaneously set to Λ(x)−ΔxB(x), and control continues with step 120. In step 118 r is set to r+1 and control returns to step 104.